import java.util.Random;

//数组中的第K个最大元素  (快排实现) 时间复杂度O(n)
//测试链接 https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
public class FindKthLargest {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums,0,nums.length-1, k);
    }

    public int quickSort(int[] nums, int l, int r, int k){
        if(l >= r){
            return nums[l];
        }
        int key = nums[new Random().nextInt(r - l + 1) + l]; //获取随机数
        int left = l - 1, right = r + 1, i = l;

        while(i < right){
            if(nums[i] == key) i++;
            else if( nums[i] < key) swap(nums, ++left, i++);
            else swap(nums,--right,i);
        }
        //排完序的结果：
        //[l, left]         < key
        //[left+1, right-1] = key
        //[right, r]        > key
        int c = r - right + 1;
        int b = right - 1 - left - 1 + 1;
        int a = left - l + 1;
        if(c >= k){ //第K大在c区间
            return quickSort(nums, right,r,k);
        }else if(b+c >= k){  //第K大在b区间
            return nums[left+1];
        }else{
            return quickSort(nums, l, left, (k-c-b)); //第K大在b区间
        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
